import org.junit.Test;

import java.util.*;

public class DP {


    public int topic198(int[] nums) {
        int[] dp = new int[nums.length]; //dp[i - 1]表示打劫前i个能获得的最大金额

        if(nums.length == 1) {
            return nums[0];
        }
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for(int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.length-1];
    }

    public int topic279(int n) {

        int[] dp = new int[n+1];

        dp[0] = 0;

        for(int i = 1; i <= n; i++) {
            int minn = Integer.MAX_VALUE;
            for(int j = 1; j * j <= i; j++) {
                minn = Math.min(minn, dp[i - j * j] + 1);
            }
            dp[i] = minn;
        }
        return dp[n];
    }

    public int topic322(int[] coins, int amount) {
        int[] dp = new int[amount + 1]; //dp[i]表示总数为i时最少需要多少硬币

        for(int i = 0; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;

        for(int i = 1; i <= amount; i++) {
            for(int j = 0; j < coins.length; j++) {
                if(coins[j] <= i && dp[i - coins[j]] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }


        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];

    }

    public int topic300(int[] nums) {
        int[] dp = new int[nums.length + 1]; //dp[i] 表示前i个最长严格递增子序列
//        int[] maxNum = new int[nums.length + 1]; //标志严格递增子序列中的最大值


        dp[0] = 1;
//        maxNum[0] = nums[0];
        for(int i = 1; i < nums.length; i++) {
            int m = 1;
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    m = Math.max(m, dp[j] + 1);
//                    maxNum[i] = nums[i];
                }
            }
            dp[i] = m;
        }

        return Arrays.stream(dp).max().getAsInt();
    }

    public int topic152(int[] nums) {

//        int[] dp = new int[nums.length + 1];    //dp[i]表示包含i的最大前i项连续子数组的积
//
//
//        for(int i = 0; i <= nums.length; i++) {
//            dp[i] = Integer.MIN_VALUE;
//        }
//        dp[0] = nums[0];
//        for(int i = 1; i < nums.length; i++) {
//
//            if(Math.abs(dp[i-1] * nums[i]) >= Math.abs(nums[i])) {
//                dp[i] = dp[i-1] * nums[i];
//            } else{
//                dp[i] = nums[i];
//            }
////            dp[i] = Math.max(Math.abs(dp[i-1] * nums[i]), Math.abs(nums[i]));
//        }
//        return Arrays.stream(dp).max().getAsInt();

        int fmax = nums[0], fmin = nums[0];
        int ans = nums[0];

        for(int i = 1; i < nums.length; i++) {
            int mx = fmax, mn = fmin;
            fmax = Math.max(Math.max(mx * nums[i], nums[i]), Math.max(mn * nums[i], nums[i]));
            fmin = Math.min(Math.min(mx * nums[i], nums[i]), Math.min(mn * nums[i], nums[i]));
            ans = Math.max(ans, fmax);
        }
        return ans;

    }

    public boolean topic139(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1]; //dp[i]表示以i结尾的字符串是否在wordDict中
        dp[0] = true;
        Set<String> wordSet = new HashSet<>(wordDict);

        for(int i = 1; i <= s.length(); i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];

    }

    public List<List<Integer>> topic118(int numRows) {

        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i <= numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for(int j = 0; j <= i; j++) {
                if(i == 0 || i == j) {
                    row.add(1);
                } else {
                    int t = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j);
                    row.add(t);
                }
            }
            res.add(row);
        }

        return res;
    }

    public boolean topic416(int[] nums) {
        if(nums.length == 1) {
            return false;
        }
        int sum = Arrays.stream(nums).sum();
        if(sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length + 1][target + 1]; //dp[i][j]表示从0-i中选出任意数和为j

        int max = Arrays.stream(nums).max().getAsInt();
        if(max > target) {
            return false;
        }
        for(int i = 0; i < nums.length; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for(int i = 1; i < nums.length; i++) {
            for(int j = 1; j <= target; j++) {
                if(nums[i] <= j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length - 1][target];
    }

    public boolean topic416_(int[] nums) {
        if(nums.length == 1) {
            return false;
        }
        int sum = Arrays.stream(nums).sum();
        if(sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        int max = Arrays.stream(nums).max().getAsInt();
        if(max > target) {
            return false;
        }
        dp[0] = true;
        dp[nums[0]] = true;
        for(int i = 1; i < nums.length; i++) {
            for(int j = target; j > 0; j--) {
                if(nums[i] <= j) {
                    dp[j] = dp[j] || dp[j - nums[i]];
                } else {
                    dp[j] = dp[j];
                }
            }

        }
        return dp[target];
    }

//    public int topic32(String s) {
//        int len = s.length();
//        if(len == 0 || len == 1) {
//            return 0;
//        }
//        int[][] dp = new int[len + 1][len + 1]; // dp[i][j]表示 i-j最长有效括号
//
//        char l = '(';
//        char r = ')';
//        for(int i = 0; i <= len; i++) {
//            dp[i][0] = 0;
//        }
//        for(int i = 1; i <= len; i++) {
//            dp[i][i] = 0;
//            for(int j = i; j <= len; j++) {
//                if(s.charAt(i) == l && r == s.charAt(j)) {
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + 1);
//                }
//            }
//        }
//
//        return dp[len][len];
//    }
    public int topic32(String s) {

        int len = s.length();
        if(len == 0 || len == 1) {
            return 0;
        }
        int[] dp = new int[len + 1];
        dp[0] = 0;
        int maxNum = 0;
        for(int i = 1; i < len; i++) {
            if(s.charAt(i) == ')') {
                if(s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }
                if(i - dp[i - 1] - 2 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2;
                }

            }
            maxNum = Math.max(maxNum, dp[i]);
        }

        return maxNum;
    }
    public int topic32_stack(String s) {

        Deque<Integer> stack = new LinkedList<>();
        stack.offer(-1);
        int maxNum = 0;

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if(stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxNum = Math.max(maxNum, i - stack.peek());
                }
            }
        }
        return maxNum;

    }

    public int topic62(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }
        for(int i = 1; i <= n; i++) {
            dp[0][i] = 1;
        }
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j - 1] +  dp[i - 1][j];
            }
        }
        return dp[m - 1][n - 1];
    }
    public int topic64(int[][] grid) {

        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < dp.length; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for(int i = 1; i < dp[0].length; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }

        for(int i = 1; i < dp.length; i++) {
            for(int j = 1; j < dp[0].length; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
            }
        }
        return dp[dp.length - 1][dp[0].length - 1];
    }

    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
//        if(m == n && m == 1) {
//            if(word1 == word2) {
//                return 0;
//            } else {
//                return 2;
//            }
//        }
        for(int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for(int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }

    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        dp[0][0] = 0;
        for(int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }
        for(int i = 1; i <= n; i++) {
            dp[0][i] = dp[0][i - 1] + s2.charAt(i - 1);
        }
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
                }
            }
        }
        return dp[m][n];
    }

    public String topic5(String s) {
        int len = s.length();
        if(len == 1) {
            return s;
        }

        int start = 0, num = 1;

        boolean[][] dp = new boolean[len + 1][len + 1];
        dp[0][0] = true;
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
//        for(int j = 1; j < len; j++) {
//            for(int i = 1; i <= j; i++) {
////                if(j - i < 3) {
////                    dp[i][j] = s.charAt(i) == s.charAt(j);
//////                    start = i;
//////                    num = Math.max(num, j - i + 1);
////                    continue;
////                }
////                if(s.charAt(i) == s.charAt(j)) {
////                    dp[i][j] = dp[i + 1][j - 1];
//////                    start = i;
//////                    num = Math.max(num, j - i + 1);
////                } else {
////                    dp[i][j] = false;
////                }
////                if(dp[i][j] && j - i + 1 > num) {
////                    num = j - i + 1;
////                    start = i - 1;
////                }
//                if(s.charAt(i - 1) != s.charAt(j - 1)) {
//                    dp[i][j] = false;
//                } else { //j - i < 3
//                    if(j - i < 3) {
//                        dp[i][j] = true;
//                    } else {
//                        dp[i][j] = dp[i + 1][j - 1];
//                    }
//                }
//                if(dp[i][j] && j - i + 1 > num) {
//                    num = j - i + 1;
//                    start = i - 1;
//                }
//            }
//        }

        for(int L = 2; L <= len; L++) {
            for(int i = 0; i < len; i++) {
                int j = i + L - 1;
                if(j >= len)
                    break;
                if(s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if(j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if(dp[i][j] && j - i + 1 > num) {
                    num = j - i + 1;
                    start = i;
                }

            }
        }
        return s.substring(start, start + num);
    }

    public int topic1143(String text1, String text2) {
        int m = text1.length(), n = text2.length();

        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;

        for(int i = 1; i <= m; i++) {
            dp[i][0] = 0;
        }
        for(int i = 1; i <= n; i++) {
            dp[0][i] = 0;
        }

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    public int topic72(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        dp[0][0] = 0;
        for(int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        for(int i = 1; i <= n; i++) {
            dp[0][i] = i;
        }

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        return dp[m][n];
    }

    public int topic136(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for(int num : nums) {
            if(set.contains(num)) {
                set.remove(num);
            } else {
                set.add(num);
            }
        }
        return (int)set.toArray()[0];
    }

    @Test
    public void test() {

        System.out.println(topic136(new int[]{2,2,1}));
    }

}

